package cn.yuemouren.tree.bst;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @Author: Timi
 * @Description: 二分搜索树
 * @Date: 2020/5/27 8:28
 */
public class BinarySearchTree<T extends Comparable<T>> {

    private class Node{
        protected Node right,left;
        protected T t;
        public Node(T t) {
            this.t = t;
            this.left = null;
            this.right = null;
        }
    }

    private Node root;
    private int size;

    public BinarySearchTree() {
        this.root = null;
        this.size = 0;
    }

    public void add(T t){
        add(root,t);
    }

    /**
     * 根据递归实现向树中插入值（如果当前值树中已存在，自动忽略）
     * @param node
     * @param t
     * @return 返回当前根节点
     */
    private Node add(Node node,T t){
        if(null == node){
            size++;
            return new Node(t);
        }
        if(t.compareTo(node.t) < 0){
            node.left = add(node.left,t);
        } else if(t.compareTo(node.t) > 0){
            node.right = add(node.right,t);
        }
        return node;
    }

    /**
     * 非递归实现向树中插入值
     * @param t
     * @param node
     */
    private void add(T t, Node node){
        if(null == node){
            node = new Node(t);
            size++;
            return;
        }
        while(true){
            if(t.compareTo(node.t) < 0){
                if(null == node.left){
                    node.left = new Node(t);
                    size++;
                    return;
                } else{
                    node = node.left;
                    continue;
                }
            } else if(t.compareTo(node.t) > 0){
                if(null == node.right){
                    node.right = new Node(t);
                    size++;
                    return;
                } else{
                    node = node.right;
                    continue;
                }
            }
        }
    }

    /**
     * 前序遍历（递归）
     */
    public void preSort(){
        preSort(root);
    }

    private void preSort(Node head){
        if(null == head){
            return;
        }
        System.out.println(head.t);
        preSort(head.left);
        preSort(head.right);
    }

    /**
     * 前序遍历非递归实现
     *      使用栈的先进先出
     */
    public void preNoSort(){
        Stack<Node> stack = new Stack<Node>();
        stack.push(root);
        while(!stack.isEmpty()){
            Node node = stack.pop();
            System.out.println(node.t);
            if(null != node.right){
                stack.push(node.right);
            }
            if(null != node.left){
                stack.push(node.left);
            }
        }
    }

    /**
     * 利用队列实现广度优先遍历
     */
    public void breadthSort(){
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            Node poll = queue.poll();
            System.out.println(poll.t);
            if(null != poll.left){
                queue.add(poll.left);
            }
            if(null != poll.right){
                queue.add(poll.right);
            }
        }
    }

    /**
     * 是否包含指定元素（递归）
     * @param t
     * @return
     */
    public boolean contains(T t){
        return contains(root,t);
    }

    private boolean contains(Node head,T t){
        if(null == head){
            return false;
        }
        if(t.compareTo(head.t) < 0){
            return contains(head.left,t);
        } else if(t.compareTo(head.t) > 0){
            return contains(head.right,t);
        } else{
            return true;
        }
    }

    public T getMin(){
        if(null == root){
            return null;
        }
        return getMin(root).t;
    }

    /**
     * 递归实现获取树中最左侧节点（最小节点）
     * @param node
     * @return
     */
    private Node getMin(Node node) {
        if(null == node.left){
            return node;
        }
        return getMin(node.left);
    }

    public T getMax(){
        if(null == root){
            return null;
        }
        return getMax(root).t;
    }

    /**
     * 递归实现获取树中最右节点（最大节点）
     * @param node
     * @return
     */
    private Node getMax(Node node) {
        if(null == node.right){
            return node;
        }
        return getMax(node.right);
    }

    public Node removeMin(){
        Node min = getMin(root);
        removeMin(root);
        return min;
    }

    /**
     * 递归实现删除树中最小值
     * @param node
     * @return
     */
    private Node removeMin(Node node) {
        if(null == node.left){
            Node rightNode = node.right;
            node.right = null;
            size--;
            return rightNode;
        }
        node.left = removeMin(node.left);
        return node;
    }

    public Node removeMax(){
        Node max = getMax(root);
        removeMax(root);
        return max;
    }

    /**
     * 递归实现删除树中最大值
     * @param node
     * @return
     */
    private Node removeMax(Node node) {
        if(null == node.right){
            Node leftNode = node.left;
            node.left = null;
            size--;
            return leftNode;
        }
        node.right = removeMax(node.right);
        return node;
    }

    public Node remove(T t){
        if(null == root){
            return null;
        }
        return remove(root,t);
    }

    private Node remove(Node node, T t) {
        if(t.compareTo(node.t) < 0){
            return node.left = remove(node.left,t);
        } else if(t.compareTo(node.t) > 0){
            return node.right = remove(node.right,t);
        } else{
            //没有右子树
            if(null == node.right){
                Node leftNode = node.left;
                node.left = null;
                size--;
                return leftNode;
            }
            //没有左子树
            if(null == node.left){
                Node rightNode = node.right;
                node.right = null;
                size--;
                return rightNode;
            }
            /**
             *这块因为删除节点左右子树均存在，所以有两种解决办法
             *      1.寻找删除节点的前驱节点
             *      2.寻找删除节点的后继节点
             */
            //1.寻找删除节点的前驱节点
            //删除左子树最大节点
            Node leftMax = removeMax(node.left);
            leftMax.left = node.left;
            leftMax.right = node.right;
            node.left = node.right = null;
            return leftMax;
            /*
            2.寻找删除节点的后继节点实现
             //删除右子树最小节点
            Node rightMin = removeMin(node.right);
            rightMin.left = node.left;
            rightMin.right = node.right;
            node.left = node.right = null;
            return rightMin;*/
        }
    }

    public int getSize(){
        return size;
    }

    public boolean isEmpty(){
        return size == 0 ? true : false;
    }
}